package SingleLinkedList;

import java.util.Stack;

/**
 * 判断一个单链表是否是回文结构：12321
 *
 * @author Liaorun
 */
public class IsPalindromeList {


    public static class Node<T> {
        public T value;
        public Node<?> next;

        public Node(T value) {
            this.value = value;
        }
    }


    /**
     * 判断一个单链表是否是回文结构：12321
     * 使用将所有的数据放到栈中来比较是不是
     * need n extra space 空间复杂度O（N)
     *
     * @param head 头节点
     * @return true 是回文，false 不是回文
     */
    public static boolean isPalindrome1(Node<?> head) {
        if (head == null || head.next == null) {
            return true;
        }

        Stack<Node<?>> stack = new Stack<>();
        Node<?> cur = head;

        // 将单链表所有的值放到栈中
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        // 正着遍历和倒着遍历比较都相等的话，就是回文结构
        // 但是需要的空间太多了,更好的办法是只把前面或者后面的数拿出来比较
        while (head != null) {
            if (head.value != stack.pop().value) {
                // 有一个不相等就不是回文结构
                return false;
            }

            head = head.next;
        }

        return true;
    }


    /**
     * 判断一个单链表是否是回文结构：12321
     * 使用快慢指针的方法，只需要 n/2大小的栈就可以了
     * 取前半截和后半截都可以
     *
     * @param head 头节点
     * @return true 是回文，false 不是回文
     */
    public static boolean isPalindrome2(Node<?> head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node<?> right = head.next;
        Node<?> cur = head;

        while (cur.next != null && cur.next.next != null) {
            // 快指针后面两个节点都有值
            // 满指针走1步
            right = right.next;
            // 快指针走2步
            cur = cur.next.next;
        }

        Stack<Node<?>> stack = new Stack<>();
        // 此时奇数个数据 right指向中间，偶数指向前一个
        // 将后半截数据放到栈中
        while (right != null) {
            stack.push(right);
            right = right.next;
        }

        while (!stack.isEmpty()) {
            if (head.value != stack.pop().value) {
                // 有一个不相等就不是回文结构
                return false;
            }
        }

        return true;
    }

    /**
     * 将单链表的后半截指针反转，然后头尾同时遍历判断是否相等，
     * 之后再把链表还原
     *
     * @param head 头节点
     * @return true 是回文，false 不是回文
     */
    public static boolean isPalindrome3(Node<?> head) {
        if (head == null || head.next == null) {
            return true;
        }

        Node<?> n1 = head;
        Node<?> n2 = head;

        while (n2.next != null && n2.next.next != null) {
            // 快指针后面两个节点都有值
            // 满指针走1步 最终:n1 -> mid
            n1 = n1.next;
            // 快指针走2步 最终:n2 -> end
            n2 = n2.next.next;
        }
        // n2 -> right part first node
        n2 = n1.next;
        // mid.next -> null
        n1.next = null;
        // 辅助右半截反转指向的节点
        Node<?> n3 = null;

        // right part convert:右边部分的指针反转
        // n2 == null 结束，前一个n1为最后一个节点
        while (n2 != null) {
            // n3 use for save next node
            n3 = n2.next;
            // next of right node convert,下一个指向前一个节点
            n2.next = n1;
            // n1, n2 向前走一步，
            // n1 move
            n1 = n2;
            // n2 move
            n2 = n3;
        }
        // n3 -> save last node
        n3 = n1;
        // n2 -> left first node
        n2 = head;

        boolean result = true;
        // check palindrome
        while (n1 != null && n2 != null) {
            if (n1.value != n2.value) {
                // 有一个不相等就不是回文结构
                result = false;
                break;
            }
            // right to mid，右边边向中间遍历
            n1 = n1.next;
            // left to mid，左边向中间遍历
            n2 = n2.next;
        }

        // n3 是最后一个，则n1是倒数第2个
        n1 = n3.next;
        // 将最后一个指向null
        n3.next = null;

        // 将反向的右半截 变回原来的样子
        // 在126行，我们把中点指向空了，所以中点为结束点
        while (n1 != null) {
            // 记录前一个
            n2 = n1.next;
            // 指向后一个
            n1.next = n3;
            // 后一个指向当前值
            n3 = n1;
            // 当前指针指向前一个
            n1 = n2;
        }

        return result;
    }

}
